马尔可夫链

Markov chain MC
马尔可夫链的思想：过去所有的信息都已经被保存到了现在的状态，基于现在就可以预测未来。

The future is independent of the past， given the present.
未来独立于过去，只基于当下。

马尔可夫链是概率论中具有马尔可夫性质且存在于离散的指数集和状态空间内的随机过程。

马尔可夫性

Markov property
马尔可夫性:
马尔科夫链为状态空间中经过从一个状态到另一个状态的转换的随机过程，该过程要求具备“无记忆性 ”，即下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。

\begin{aligned} P {X (t_{n}) \leq x ∣ X (t_{1}) = x_{1}, \dots, X (t_{n - 1}) = x_{n - 1}} \\ = P {X (t_{n}) \leq x_{n} ∣ X (t_{n - 1}) = x_{n - 1}} \end{aligned}

条件分布函数

一步转移概率

\begin{array}{r} P_{i j} = P {X_{t + 1} = a_{j} ∣ X_{t} = a_{i}} \end{array}

此条件概率称为马氏链在时刻 $t$ 处于状态 $a_{i}$ 条件下，在时刻 $t + 1$ 转移到状态 $a_{j}$ 的转移概率

链在时刻 $t$ 从任何一个状态 $a_{i}$ 出发，到另一个时刻 $t + 1$ 必然转移到 $a_{1}, a_{2}, \dots$ 各个状态中的某一个：

\begin{array}{r} \sum_{j = 1}^{+ \infty} p_{i j} = 1 \end{array}

由转移概率组成的无穷维矩阵 $P (m, m + n) = (P_{i j} (m, m + n))$ 称为转移概率矩阵

当状态空间为有限集时， $P$ 就为有限矩阵，阶数等于状态空间的状态数

\begin{array}{r} P = (\begin{array}{c} p_{11} & p_{12} & \dots & p_{1 j} & \dots \\ p_{21} & p_{22} & \dots & p_{2 j} & \dots \\ ⋮ & ⋮ & ⋮ \\ p_{i 1} & p_{i 2} & \dots & p_{i j} & \dots \\ ⋮ & ⋮ & ⋮ \end{array}) \end{array}

\begin{aligned} \begin{array}{c} a_{1} & a_{2} & \dots & a_{j} & \dots \end{array} \\ \begin{array}{c} a_{1} \\ a_{2} \\ ⋮ \\ a_{i} \\ ⋮ \end{array} (\begin{array}{c} p_{11} & p_{12} & \dots & p_{1 j} & \dots \\ p_{21} & p_{22} & \dots & p_{2 j} & \dots \\ ⋮ & ⋮ & ⋮ \\ p_{i 1} & p_{i 2} & \dots & p_{i j} & \dots \\ ⋮ & ⋮ & ⋮ \end{array}) \end{aligned}

基本应用

随机游动模型
 排队论

用于动力系统、化学反应、排队论、市场行为和信息检索的数学建模

马尔可夫链可被应用于蒙特卡洛方法中，
形成马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）

此外作为结构最简单的马尔可夫模型（Markov model）
一些机器学习算法，以马尔可夫链为理论基础，例如
隐马尔可夫模型（Hidden Markov Model, HMM）
马尔可夫随机场（Markov Random Field, MRF）
马尔可夫决策过程（Markov decision process, MDP）